# @Author: Eric Ito
# @Date: 1/29/2009
# @Name: Project Euler Problem 35


"""
The number, 197, is called a circular prime because all rotations
of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100:

2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?
"""

from util import isPrime
from util import getPrimes

PRIMES = getPrimes(1000000)

def rotate(num):
    #returns list of rotations
    rotations = []
    if len(num) == 1:
        rotations.append(int(num))
        return rotations
    elif len(num) > 1:
        temp = num
        while 1:
            temp = temp[-1] + temp[:-1]
            rotations.append(temp)
            if temp == num:
                return rotations

def isCircularPrime(n):
    rots = rotate(str(n))

    for r in rots:
        if not int(r) in PRIMES:
            return False
    return True

def main():
    cir_count = 0
    for i in PRIMES:
        if isCircularPrime(str(i)):
           cir_count += 1
    print cir_count


if __name__ == "__main__":
    main()